import java.util.ArrayList;
import java.util.List;

public final class Exacto extends Ejercicio
{
	public int[] Vo1, Vo2;
	private int cruces;
	double tiempoInicio, tiempoFin;
	
	protected Resultado DGIB
	(
			int n1, int v1[], int n2, int v2[], int m, Eje v1v2[],
			int np1, int vp1[], int np2, int vp2[], int mp, Eje vp1vp2[]
	){
		Resultado res = new Resultado();
		
		tiempoInicio = System.currentTimeMillis();
		
		int i, N1 = n1+np1, N2 = n2+np2, M = m+mp;
		Nodo[] V1 = new Nodo[n1], V2 = new Nodo[n2], VP1 = new Nodo[np1], VP2 = new Nodo[np2];
		Eje[] V1V2 = new Eje[M];
		
		for( i = 0; i < n1; i++ )
			V1[i] = new Nodo(v1[i],false);
		
		for( i = 0; i < np1; i++ )
			VP1[i] = new Nodo(vp1[i],true);
		
		for( i = 0; i < n2; i++ )
			V2[i] = new Nodo(v2[i],false);
		
		for( i = 0; i < np2; i++ )
			VP2[i] = new Nodo(vp2[i],true);
		
		for( i = 0; i < m; i++ )
			V1V2[i] = v1v2[i];
		
		for( i = 0; i < mp; i++ )
			V1V2[m+i] = vp1vp2[i];
		
		//cruce maximo de ejes
		this.cruces = M*(M-1);
		//solucion optima
		this.Vo1 = new int[N1];
		this.Vo2 = new int[N2];
		
		permutar
		(
			v1,n1,
			vp1,np1,
			v2,n2,
			vp2,np2,
			V1V2, M, np1
		);
		
		//tiempoFinal = System.currentTimeMillis();
		
		//double tiempo = (tiempoFinal - tiempoInicio);
		
		res.kid = this.cruces;
		res.n_iv1 = N1;
		res.iv1 = this.Vo1;
		res.n_iv2 = N2;
		res.iv2 = this.Vo2;
		res.time = 5;
		return res;
	}
	
	public void permutar
	(
			int[] v1, int n1, 
			int[] vp1, int np1,
			int[] v2, int n2,
			int[] vp2, int np2,
			Eje[] V1V2, int M,
			int l
	){ 
		if( l > 1 )
		{
			for( int i = 0; i < l; i++ )
			{
				swap(vp1,i,l-1);
				
				permutar(v1,n1,vp1,np1,v2,n2,vp2,np2,V1V2,M, l-1);
				
				swap(vp1, i, l-1);
			}
		}
		else
		{
			int[] arrInd = new int[np1];
			lugares(v1,n1,vp1,np1,v2,n2,vp2,np2,V1V2,M, 0, 0,arrInd);
		}
	}
	
	public void permutar
	(
		int[] V1, int N1,
		int [] v2, int n2,
		int[] vp2, int np2,
		Eje[] V1V2, int M,
		int l			
	)
	{
		if( l > 1 )
		{
			for( int i = 0; i < l; i++ )
			{
				swap(vp2,i,l-1);
				
				permutar(V1,N1,v2,n2,vp2,np2,V1V2,M, l-1);
				
				swap(vp2, i, l-1);
			}
		}
		else
		{
			int[] arrInd = new int[np2];
			lugares(V1,N1,v2,n2,vp2,np2,V1V2,M,0,0,arrInd);
		}	
	}
	
	public void lugares
	(
			int[] v1, int n1, 
			int[] vp1, int np1,
			int[] v2, int n2,
			int[] vp2, int np2,
			Eje[] V1V2, int M,
			int ind, int nro,int[]arrInd	
	)
	{
		int i=0, j = 0, actual = 0, pos = 0;
		while(nro <= n1)
		{
			arrInd[ind] = nro;
			if(ind < np1-1)
			{
				lugares(v1,n1,vp1,np1,v2,n2,vp2,np2,V1V2,M, ind + 1, nro,arrInd);
			}
			else
			{
				i = 0; j = 0; actual = 0; pos = 0;
				int N1 = n1+np1;
				int[] V1 = new int[N1];
				
				for(int k = 0; k < N1; k++)
				{
					if(j < np1 && arrInd[pos] == actual)
					{
						V1[k] = vp1[j];
						j++;
						if(pos < np1 - 1)
							pos++;
					}
					else if(i < n1)
					{
						V1[k] = v1[i];
						i++;
						actual++;
					}
				}
				
				int cantejes = 0;
				List <Eje> ejes = new ArrayList <Eje>();
				
				for(int h = 0; h < M; h++)
				{
					if( esta(v1,V1V2[h].origen) || esta(vp1,V1V2[h].origen) )
					{
						if( esta(v2 ,V1V2[h].destino) )
						{
							ejes.add(V1V2[h]);
							cantejes++;
						}
					}
				}
				
				Eje [] V1V2tmp = new Eje[cantejes];
				
				for(int h = 0; h < cantejes; h++)
				{
					V1V2tmp[h] = ejes.get(h);
				}
				
				//Esta vendria a ser la poda...
				if( cantidadCruces(V1,N1,v2,n2,V1V2tmp,cantejes) < cruces )
				{
					permutar(V1,N1,v2,n2,vp2,np2,V1V2,M,np2);
				}
			}
			nro++;
		}
	}
	
	public void lugares
	(			
			int[] V1, int N1, 
			int[] v2, int n2,
			int[] vp2, int np2,
			Eje[] V1V2, int M,
			int ind, int nro,int[]arrInd
	){
		int i=0, j = 0, actual = 0, pos = 0;
		
		while(nro <= n2)
		{
			arrInd[ind] = nro;
			if(ind < np2-1)
			{
				lugares(V1,N1,v2,n2,vp2,np2,V1V2,M, ind+1, nro,arrInd);
			}
			else
			{
				i = 0; j = 0; actual = 0; pos = 0;
				int N2 = n2+np2;
				int[] V2 = new int[N2];
				
				for(int k = 0; k < N2; k++)
				{
					if(j < np2 && arrInd[pos] == actual)
					{
						V2[k] = vp2[j];
						j++;
						if(pos < np2 - 1)
							pos++;
					}
					else if(i < n2)
					{
						V2[k] = v2[i];
						i++;
						actual++;
					}
				}
				
				int c = cantidadCruces(V1,N1,V2,N2,V1V2,M);
				
				if(c < cruces)
				{
					cruces = c;
					System.arraycopy(V1, 0, this.Vo1, 0, N1); 
					System.arraycopy(V2, 0, this.Vo2, 0, N2); 
				}
			}
			nro++;
		}	
	}
}

